package com.nowcoder.code.lcof;

import com.algorithm.model.TreeNode;
import com.algorithm.model.TreeNodeService;

public class JZ26 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeService.getTree();
        TreeNode treeNode1 = TreeNodeService.getTree();
        treeNode1.left = new TreeNode(2);
//        TreeNodeService.print(treeNode);
        System.out.println(new JZ26().HasSubtreeR(treeNode, treeNode1));
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return HasSubtreeR(root1, root2);
    }
    public boolean HasSubtreeR(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }

        if (root1.val == root2.val &&
                HasSubtreeR(root1.left, root2.left) && HasSubtreeR(root1.right, root2.right)) {
            return true;
        }

        return HasSubtreeR(root1.left, root2) || HasSubtreeR(root1.right, root2);
    }


}
